package 递归回溯;

import com.alibaba.fastjson.JSON;
import 我的JDK基础数据结构.HashMap.HashMap;

import java.util.ArrayList;
import java.util.List;
import java.util.Map;
import java.util.TreeMap;

public class JZ60n个骰子的点数 {

    /**
     * 把n个骰子扔在地上，所有骰子朝上一面的点数之和为s。输入n，打印出s的所有可能的值出现的概率。
     * 你需要用一个浮点数数组返回答案，其中第 i 个元素代表这 n 个骰子所能掷出的点数集合中第 i 小的那个的概率。
     *
     * 示例 1:
     * 输入: 1
     * 输出: [0.16667,0.16667,0.16667,0.16667,0.16667,0.16667]
     * 示例 2:
     * 输入: 2
     * 输出: [0.02778,0.05556,0.08333,0.11111,0.13889,0.16667,0.13889,0.11111,0.08333,0.05556,0.02778]
     *  
     * 限制：
     * 1 <= n <= 11
     */

    /**
     * 动态规划难点在于如何将题目抽象为状态转移数组;
     * 动态转移方程
     * [i][j]=sum([i-1][j-6]+[i-1][j-5]+[i-1][j-4]+[i-1][j-3]+[i-1][j-2]+[i-1][j-1])
     * 第n个骰子组成的 num 点的个数 就是前n-1个骰子 组成 sum(num-1,num-2,num-3,num-4,num-5,num-6)的和
     */

    public double[] dicesProbability(int n) {


        int[][] dp=new int[n][(n)*6];

        //base
        for (int i = 0; i < 6; i++) {
            dp[0][i]=1;
        }

        //投n个骰子
        for (int i = 1; i < n; i++) {
            int length=(i+1)*6-1;
            for (int j = i; j <= length; j++) {
                //当前次数的 [上一个前6个次数和]
                int sum=0;
                for (int k = 1; k <= 6; k++) {
                    if(j-k<0){
                        break;
                    }
                    sum+=dp[i-1][j-k];
                }
                dp[i][j]=sum;
            }
        }

        int count=0;
        for (int i = 0; i < dp[n-1].length; i++) {
            count+=dp[n-1][i];
        }

        List<Double> list=new ArrayList<>();

        for (int i = 0; i < dp[n - 1].length; i++) {
            double result=((double) dp[n-1][i])/((double)count);
            if(result!=0){
                list.add(result);
            }
        }

        double[] result=new double[list.size()];

        for (int i = 0; i < list.size(); i++) {
            result[i]=list.get(i);
        }

        return  result;
    }

    //超时解法
    private TreeMap<Integer,Integer> map=new TreeMap<>();
    private int count=0;
    private int n;

    public double[] dicesProbabilityBad(int n) {

        this.n=n;
        dfs(0,0);

        int index=0;
        double[] result=new double[map.size()];

        for (Map.Entry<Integer, Integer> entry : map.entrySet()) {
            double s=((double)entry.getValue())/((double)count);
            result[index++]=s;
        }

        return result;
    }

    private void dfs(int sum,int index) {
        if(index==this.n){
            map.put(sum,map.getOrDefault(sum,0)+1);
            count++;
            return;
        }

        for (int i = 1; i <= 6; i++) {
            dfs(sum+i,index+1);
        }

    }

    public static void main(String[] args) {
        JZ60n个骰子的点数 jz=new JZ60n个骰子的点数();
        double[] result1 = jz.dicesProbabilityBad(1);
        System.out.println(JSON.toJSONString(result1));
        double[] result2 = jz.dicesProbability(1);
        System.out.println(JSON.toJSONString(result2));
    }

}
